#include <vector>
#include <iostream>

using namespace std;

template<typename T>
void bubbleSort(vector<T> vec){
	T temp;
	vector<T>::iterator it;
	for(int i = 0; i = vec.size(); i ++){
		it = vec.begin();
		while(it != vec.begin() + i){
			//if()
		}
	}
}

template <typename T>
void bubbleSort(T arr[], size_t size){
	T temp;
	bool flag = true;
	for(size_t i = size - 1; i > 0; i --){
		temp = arr[i];
		flag = true;
		/*for(size_t j = 0; j < i; j ++){
			if(arr[j] > arr[i]){
				temp = arr[j];
				arr[i]
			}
		}*/
		
		for(size_t j = 0; j < i; j ++){
			if(arr[j] > arr[j + 1]){
				temp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = temp;
				flag = false;
			}
		}
		if(flag)
			break;
	}
}

void testBubbleSort(){
	// int arr[] = {3, 2, 5, 6, 9, 1, 4, 8, 10, 12};
	int arr[] = {1, 1, 1, 2, 1, 1, 1};
	int size = sizeof(arr) / sizeof(int);
	bubbleSort(arr, size);

	int index = 0;
	while(index < size)
		cout << arr[index ++] << endl;
	getchar();
}